package top.minuy.structure.tree.unifind;

/**
 * Quick Find
 * 简单并查集，使用数组模拟并查集
 *
 * @author Minuy
 * @time 22:07
 * @date 2021/10/28
 */
public class UnionFindV1 implements UF {
    int[] id;

    public UnionFindV1(int size) {
        id = new int[size];
    }

    /**
     * 获取并查集大小
     *
     * @return 并查集当前大小
     */
    @Override
    public int getSize() {
        return id.length;
    }

    /**
     * 查找val的ID
     *
     * @param val 要查找的元素
     * @return 被查元素的ID
     */
    private int find(int val) {
        if (val < 0 || val >= id.length) {
            throw new IllegalArgumentException("Find failed. Index is illegal.");
        }
        return id[val];
    }

    /**
     * 判断p和q是否连接
     *
     * @param p 元素1
     * @param q 元素2
     * @return 连接或者不连接
     */
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 将p和q所属的集合相连接
     *
     * @param p 元素1
     * @param q 元素2
     */
    @Override
    public void unionElements(int p, int q) {
        int pId = find(p);
        int qId = find(q);

        if (qId == pId) {
            return;
        }

        for (int i = 0; i < id.length; i++) {
            if (id[i] == qId) {
                id[i] = pId;
            }
        }
    }
}
